學習資源

https://labuladong.online/algo/data-structure-basic/linkedlist-basic/

學習記錄

今天是學習的第 18 天，主要學習了用陣列加強哈希表（ArrayHashMap）：

添加 randomKey() API

如果我們想在基於哈希表的 API 之上，新增一個 randomKey() API，可以在 O(1) 的時間複雜度內返回一個隨機的鍵，這件事並沒有那麼地容易。

為什麼直接從哈希表隨機取鍵很困難

1. 開放尋址法：底層陣列有空洞，隨機索引可能指向空位置
2. 拉鏈法：不僅要隨機陣列索引，還要隨機鏈表節點，且無法保證均勻隨機
3. 時間複雜度問題：遍歷查找、重複隨機等方法都無法達到 O(1)

解決思路

使用額外的陣列來儲存所有鍵，結合哈希表建立雙向映射：

• 陣列 arr：按順序儲存所有鍵值對 key-value 節點
• 哈希表 map：建立 key -> 陣列索引 的映射關係

O(1) 刪除陣列元素

普通陣列刪除中間元素需要移動資料，時間複雜度是 O(n)，解決方案：

1. 將待刪除元素與陣列最後一個元素交換位置
2. 刪除陣列尾部元素（O(1)操作）
3. 更新哈希表中交換元素的索引映射

class MyArrayHashMap {
    constructor() {
        this.map = new Map();  // key -> 陣列索引
        this.arr = [];         // 儲存所有 key-value 節點
    }
    
    put(key, val) {
        if (this.containsKey(key)) {
            // 修改現有值
            let i = this.map.get(key);
            this.arr[i].val = val;
        } else {
            // 新增：加到陣列尾部，建立映射
            this.arr.push(new Node(key, val));
            this.map.set(key, this.arr.length - 1);
        }
    }
    
    remove(key) {
        // 交換到尾部 -> 刪除尾部 -> 更新映射
        let index = this.map.get(key);
        let lastElement = this.arr[this.arr.length - 1];
        
        this.arr[index] = lastElement;
        this.map.set(lastElement.key, index);
        
        this.arr.pop();
        this.map.delete(key);
    }
    
    randomKey() {
        let randomIndex = Math.floor(Math.random() * this.arr.length);
        return this.arr[randomIndex].key;
    }
}

學習總結

• 透過交換元素到尾部，達到刪除陣列元素 O(1) 的時間複雜度
• 通過雙向映射來維護資料結構間的一致性